package com.itheima.leetcode;

import java.util.Arrays;

/**
 * 字符串匹配 - Knuth Morris Pratt 算法(双指针+动态规划)
 */
public class StrStrLeetcode28KMP {

    /**
     * 双指针
     * @param haystack
     * @param needle
     * @return
     */
    static int strStr(String haystack, String needle) {
        char[] origin = haystack.toCharArray(); // 原始
        char[] pattern = needle.toCharArray();  // 模式
        int[] lsp = lps(pattern);               // 最长前后缀数组
        /*
            1. 匹配成功，i++ j++, 直到 j== 模式字符串长度
            2. 匹配失败
                j == 0 则 i++
                j ！= 0 跳过最长前后缀字符，继续匹配
         */
        int i = 0;
        int j = 0;
        while (pattern.length - j <= origin.length - i) {
            if (origin[i] == pattern[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = lsp[j - 1];
            }

            if (j == pattern.length) {
                // 找到解
                return i - j;
            }
        }
        return -1;
    }

    /**
     * 动态规划思想
     * <p>
     * 最长前后缀数组：只限模式字符串相关
     * <p>
     * 1. 索引：使用了模式字符串前 j 个字符串 - 1
     * <p>
     * 2. 值：最长前后缀的长度（恰好是下一次j要跳转的位置）
     * <p>
     * 视频里这里讲的不好,建议参考<a href="https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.1387.favlist.content.click&vd_source=9da584380747b8d9eac52dce93a4a798">视频</a>
     *
     * @param pattern
     * @return
     */
    public static int[] lps(char[] pattern) {
        int[] lps = new int[pattern.length];
        int i = 1; // 数组从 1 开始，index 0 只能是 0
        int j = 0; // 当前共同前后缀的长度(注意是长度，不是坐标，默认为0,j的长度不会超过i+1)
        while (pattern.length > i) {
            if (pattern[i] == pattern[j]) {
                lps[i] = j + 1;
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                /*
                    数组是包含了以下情况的
                    A B A B A
                    A B A
                        A B A
                 */
                j = lps[j - 1];
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        /*System.out.println(strStr("ababababcabacacababaca",
                "ababaca"));
        System.out.println("ababababcabacacababaca".indexOf("ababaca"));*/
        System.out.println(Arrays.toString(lps("ababaca".toCharArray())));
    }
}
